D - We Love ABC

組み合わせのこういう系統の問題はDPっぽい！！→DPです。

なんか、n文字目までの組み合わせの数、みたいなのでよくあるDPができそうだと思いました

学んだ思考

3種類が順番に並ぶ系は、真ん中を固定すると考えやすかったりする

DP解法

まず一旦、

で考えてみます。基本的なDPはよく1つ目の添字が「i文字目までで…」みたいなのになることが多いです。

次に遷移を考えていきます。遷移の考え方としては、n番目までの計算結果を使ってn+1番目が求められるか？みたいな考え方をします。今回の場合だと、「0~5文字目までのABC数が分かっていたら、6文字の時のABC数をいい感じに求められるか？」みたいな感じです。

でも、流石にそれぞれのABC数だけで次のABC数を作り出すのは難しそうです。

なぜなら同じABC数でも、次の文字がCだったときに

AAAAABBBBB + C → ABC数は25になる

AAAAAAAAAA + C → ABC数は0のまま

のように結果が変わってくるからです。このままでは状態が足りないので、状態を足していくことにします。

ABCの組み合わせを直接求めるのは難しそうなので（紙考察をしてみると）、Aまでを作る組み合わせ、ABまでを作る組み合わせ、ABCまでを作る組み合わせ、と分けて考えることにします。そうすれば少しは考えやすくなります。たぶん。

何も選ばない組み合わせの数→つまりできる文字列の数

"A"の数

"AB"の数

"ABC"の数

という風な4つに分けて考えていけばよいです。